//============================================================================
// Name        : GSP295_Wk2_MergeSort.cpp
// Author      : Ronald Ram
// Version     :
// Copyright   : GSP295 Wk2 Program - MergeSort
// Description : Doubly Linked List, used to store string for Merge Sort in C++
//============================================================================

#include "DoublyLinkedList.h"
#include <ctype.h>

namespace GSP295_Wk2_MergeSort
{
	//C001: DEFAULT CONSTRUCTOR
	DoublyLinkedList::DoublyLinkedList()
	{
		head = NULL;
		last = NULL;
		count = 0;
	}
	
    //C002: DESTRUCTOR
	DoublyLinkedList::~DoublyLinkedList()
	{
		Clear();
	}

	//M001: Add string to Linked List
    void DoublyLinkedList::Add(string input)
    {
		Node *newNode;
    	Node *temp = NULL;

    	for (int i=0; i< (int)input.size(); ++i)
    	{
			newNode = new Node();
    		newNode->data = input[i];
			++count;

    		//Linked List is Empty
    		 if ( isEmpty() )
    		{
				newNode->prev = newNode->next = NULL;
    			head = last = newNode;
    		}
    		//1 node in Linked List
    		else if ( last == head )
    		{
				last = newNode;  
				head->next = last;  
				
				last->prev = head;  
				last->next = NULL;
    		}
    		//2+ nodes in Linked List
    		else
    		{
				temp = last;  
				last = newNode;  
				
				temp->next = last; 
				last->prev = temp;  
				last->next = NULL;
			}
		}
    }

    //M002: Add Node to Linked List
	void DoublyLinkedList::Add ( Node node )
	{
		Node *newNode = new Node();
		newNode->data = node.data;

		//Linked List is Empty
		if ( isEmpty() )
		{
			head = last = newNode;
			head->next = last->next = NULL;
			head->prev = last->prev = NULL;
		}
		//1+ nodes in Linked List
		else
		{
			Node *temp = last;

			last = newNode;
			temp->next = last;
			last->prev = temp;
			last->next = NULL;
		}
	}

	//M003: MergeSort Algorithm to sort a list of 'ALPHA NUMERICS' in alphabetically order
	//Sort Order is from A-Z
    void DoublyLinkedList::MergeSort()
    {
    	head = MergeSort(head);
		
		last = head;
		Node *temp = head;

		//Update 'last' point to last node in the list
		while ( last != NULL)
		{
			last = last->next;
		}
    }

	//PRE-CONDiTN: method takes a list input
	//FUNCTION: 
	//>>>>Firstly, breaks the list in single nodes
	////>>>>Secondly, sorts nodes in sorted order and merges them until there are only two lists, left
	////>>>>Thirdly, sends the two sorted list into Merge(leftList, rightList) method to be sorted and merged into one big list
	//POST-CONDiTN: method returns a fully sorted and merged list
	Node* DoublyLinkedList::MergeSort( Node *list )
	{
		//List is Empty,OR 1 Node in List
		if ( (list == NULL) || (list->next == NULL) ) { return list;
		}
		//2+ Nodes in List
		else 
		{
			Node *right = NULL;
			Node*midR = list, *currR = list->next;
			Node *left = list;

			//curr2 points to 3rd Node
			if ( currR != NULL ) { currR = currR->next; }

			//Locate the median Node in List
			while ( currR != NULL )
			{
				midR = midR->next;
				currR = currR->next;
				//curr2 points to 3rd Node
				if ( currR != NULL ) { currR = currR->next; }
			}
			//Split the 'list' into two lists
			right = midR->next;
			right->prev = NULL;
			midR->next = NULL;

			//Further Split the lists, until there are single nodes
			left = MergeSort(left);
			right = MergeSort(right);

			return ( Merge(left, right) );
		}
	}

	//Sort & Merge the two divided lists
	//PRE-CONDiTN: method takes two list inputs
	//FUNCTION: method compares two lists and sorts it in the smallest->largest values
	//POST-CONDiTN: returns a sorted and merged list
	Node* DoublyLinkedList::Merge( Node *left, Node *right)
	{
		Node *result = NULL;
		Node *curr = NULL, *temp = NULL;
		
		//Check if Left list is Empty
		if ( left == NULL ) { result = right;
		} 
		//Check if Right list is Empty
		else if ( right == NULL ) { result = left;
		}
		else
		{
			//Check first Node in Left and Right lists
			if ( (Letter)left->data < (Letter)right->data ) 
			{
				result = left;  left = left->next;
			} 
			//Check if right is < left || Right = Left
			else
			{
				result = right;  right = right->next;
			}
			
			//Update 'curr' point to head of merge list
			curr = result;

			while( left != NULL && right !=NULL )
			{
				//Update 'temp' point to latest curr node
				temp = curr;

				//Check if left is < right || left = right
				if ( ((Letter)left->data < (Letter)right->data) || ((Letter)left->data == (Letter)right->data) ) 
				{
					curr = left;
					left = left->next;
					//Link prev, next nodes
					curr->prev = temp;
					temp->next = curr;
				} 
				//Check if right is < left
				else
				{
					curr = right;
					right = right->next;
					//Link prev, next nodes
					curr->prev = temp;
					temp->next = curr;
				}
			}//while

			//Update 'temp' point to latest curr node
			temp = curr; 

			//Left list is exhausted
			if ( left == NULL ) 
			{ 
				curr = right;
				//Link prev, next nodes
				curr->prev = temp;
				temp->next = curr;
			} 
			//Right list is exhausted
			else 
			{
				curr = left;
				//Link prev, next nodes
				curr->prev = temp;
				temp->next = curr;
			}
		}

		return result;
	}


	
	//Methods returns a copy of the Linked list
	Node* DoublyLinkedList::copyList()
	{
		Node *list1 = NULL, *node=NULL, *curr=NULL, *temp=NULL;

		curr = head;
		list1->prev = NULL;
		
		//copy list to list1
		while ( curr != NULL )
		{
			node = new Node();
			node->data = curr->data;
			if ( list1 == NULL ) 
			{
				node->prev = node->next = NULL;
				temp = list1 = node;
			}
			else
			{
				node->next = NULL;
				temp->next = node;
				temp = node;
			}
			curr = curr->next;
		}

		return list1;
	}


    //M004: Delete all nodes in Linked List
    void DoublyLinkedList::Clear()
    {
    	Node *oldNode = NULL;

    	while (head != NULL)
    	{
    		oldNode = head;		//oldNode takes head Position,
    		head = head->next;	//head now points to next Node in list
    		delete oldNode;		//Delete the first Node in list
			--count;
    	}
		head = last = NULL;
    }

    //M005: Print all data in Linked List
	void DoublyLinkedList::Print ( )
	{
		cout << "\n===============================\n" << endl;

		if ( !isEmpty() )
		{
			Node *curr = head;

			cout << "RESULTS: ";
			
			do
			{
				cout << curr->data << " ";

				if ( curr->next != NULL ) { curr = curr->next;
				}
				else { curr = NULL; }
			}
			while ( curr != NULL );

			cout << "\n\n>>> Node Count: " << count << " <<<" << endl;
		}
		else 
		{ 
			cout << "\n>>> RESULT: List is Empty <<<" << endl;
		}
		cout << "\n===============================\n\n\n\n" << endl;
	}

    //M006: T/F if Linked List is Empty
    bool DoublyLinkedList::isEmpty() const 
	{ 
		return (head == NULL); 
	}
}
